package data_structures_and_algorithms.tree.learn;

import common.TreeNode;

/**
 * @ClassName Code_zuo_god_inorderSuccessor
 * @Description:  找到给定节点的后继节点
 *
 * 设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
 *
 * 如果指定节点没有对应的“下一个”节点，则返回null。
 *
 * 示例 1:
 *
 * 输入: root = [2,1,3], p = 1
 *
 *   2
 *  / \
 * 1   3
 *
 * 输出: 2
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,null,1], p = 6
 *
 *       5
 *      / \
 *     3   6
 *    / \
 *   2   4
 *  /
 * 1
 *
 * 输出: null
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/successor-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/30 17:15
 */
public class Code_zuo_god_inorderSuccessor {

    public class TreeNode{
        public  int val;

        public  TreeNode left;

        public  TreeNode right;

        public TreeNode parent;

        public TreeNode(int val){
            this.val = val;
        }
    }

    /**
     * 做题思路：熟练掌握中序遍历的顺序结构关系
     *
     * 1、如果给定节点P有右孩子，那么下一个节点一定是右孩子的最左孩子节点
     *
     * 2、如果给定节点P没有右孩子，那么下一个节点一定往上找的所有父节点链中属于左孩子的节点的父节点，如果找不到 则说明不存在下一个节点（给定节点就是最后一个节点）
     */
    // 给定一个P节点，找到在中序遍历中的下一个节点（这种节点中给出了parent指向，我们可以根据节点P找到整个二叉树）
    public TreeNode inorderSuccessor(TreeNode p) {
        if (p == null)
            return null;
        TreeNode ans = null;
        if (p.right == null){
            // 没有右孩子节点
            TreeNode parent = p.parent, node = p;
            while (parent != null){
                if (parent.left == node)
                    break;
                node = parent;
                parent = parent.parent;
            }
            ans = parent;
        }else {
            // 有右孩子节点
            TreeNode node = p.right;
            while (node.left != null){
                node = node.left;
            }
            ans = node;
        }
        return ans;
    }
}
